package com.my.leetCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author Lelezhang
 * @create 2021-07-19 21:47
 */
public class LeetCode283 {
    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * <p>
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 示例 2:
     * <p>
     * 输入: nums = [0]
     * 输出: [0]
     * <p>
     * <p>
     * 链接：https://leetcode-cn.com/problems/two-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static void main(String[] args) {
        // 双指针，左指针指向0，右指针指向非0
        // 当左指针指向0，右指针指向非0时，交换，左指针右移，右指针右移
        int right = 0;
        int left = 0;
        int[] nums = {0, 1, 0, 3, 12};
        int n = nums.length;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
//        Arrays.stream(nums).forEach(System.out::println);
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }


    // 采用哈希表
    public static int[] twoSum02(int[] nums, int target) {
        HashMap<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
        // 将数据存入哈希表
        for (int i = 0; i < nums.length; i++) {
            numsMap.put(nums[i], i);
        }
        //寻找target
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (null != numsMap.get(temp)) {
                return new int[]{i, numsMap.get(temp)};
            }
        }
        return new int[2];
    }
}
